from functools import lru_cache

def fibonacci(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


@lru_cache
def fibonacci2(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci2(n - 1) + fibonacci2(n - 2)

def fibonacci3(n):
    a,b=0,1
    for _ in range(n-1):
        a,b=b,a+b
    return a
